package q486_PredictTheWinner;

public class Solution {
    public boolean PredictTheWinner(int[] nums) {
        return total(nums, 0, nums.length - 1, 1) >= 0;
    }

    /*
    在博弈的过程中 需要引入turn的变量
    考虑到具有两位玩家 玩家每次都希望利益最大化
    我们假设我们赢得条件是 我们的总数 >= 对手的总数 意味着两者的差 >= 0
    因此作为P1 我们首先turn1时，可以选取数组两端的一个数字 此时对于我们的总收益是一个正向的作用 turn因此为+1
    而到P2时，对手取得的数字对我们是一个负的收益 因此turn变为-1
    最后形成一个迭代的过程 在所有的结果中找出一个最大值 看是否能够 >= 0
     */
    public int total(int[] nums, int start, int end, int turn) {
        if (start == end) {
            return nums[start] * turn;
        }
        int scoreStart = nums[start] * turn + total(nums, start + 1, end, -turn);
        int scoreEnd = nums[end] * turn + total(nums, start, end - 1, -turn);
        return Math.max(scoreStart * turn, scoreEnd * turn) * turn;
    }

}
